package main

import "fmt"

func main() {
	fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))
}

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	res := [][]int{}
	for base := 0; base < len(nums)-2; base++ {
		if base > 0 && nums[base] == nums[base-1] {
			continue
		}
		low := base + 1
		high := len(nums) - 1
		sum := 0 - nums[base]
		for low < high {
			if nums[low]+nums[high] == sum {
				res = append(res, []int{nums[base], nums[low], nums[high]})
				for low < high && nums[low] == nums[low+1] {
					low++
				}
				for low < high && nums[high] == nums[high-1] {
					high--
				}
				low++
				high--
			} else if nums[low]+nums[high] < sum {
				low++
			} else {
				high--
			}
		}
	}
	return res
}

func partition(a []int, lo int, hi int) int {
	i := lo - 1
	for j := lo; j < hi; j++ {
		if a[j] < a[hi] {
			i++
			a[j], a[i] = a[i], a[j]
		}
	}
	a[hi], a[i+1] = a[i+1], a[hi]
	return i + 1
}

func quicksort(a []int, lo int, hi int) {
	if lo >= hi {
		return
	}
	p := partition(a, lo, hi)
	quicksort(a, lo, p-1)
	quicksort(a, p+1, hi)
}
